/// [Circular primes](https://projecteuler.net/problem=35)
use std::collections::HashMap;

fn main() {
    let max = 1_000_000;
    let rst = find_circular(max);
    println!("The number of circular primes below one million: {}", rst.len());
}

fn find_primes(max: usize) -> Vec<usize> {
    let mut stat = vec![true; max + 1];
    let mut list = vec![];
    for n in 2..max {
        if stat[n] {
            list.push(n);
            for i in 2..=(max / n) {
                stat[n * i] = false;
            }
        }
    }
    list
}

fn find_circular(max: usize) -> Vec<usize> {
    let primes = find_primes(max);
    let mut maps = HashMap::new();
    let mut list = vec![];
    for &prime in primes.iter() {
        if let None = maps.get(&prime) {
            let mut stat = true;
            for item in find_rotations(prime) {
                if !primes.contains(&item) {
                    stat = false;
                    break;
                }
            }
            if stat {
                list.push(prime);
                maps.insert(prime, ());
            }
        }
    }
    list
}

fn find_rotations(num: usize) -> Vec<usize> {
    let mut list = vec![];
    let mut buff = num.to_string();
    for _ in 1..buff.len() {
        if let Some(c) = buff.pop() {
            buff = format!("{}{}", c, buff);
            list.push(buff.parse().unwrap());
        }
    }
    list
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn primes() {
        assert_eq!(find_primes(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
    }
    #[test]
    fn circular() {
        assert_eq!(find_circular(100), vec![2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97]);
    }
    #[test]
    fn rotations() {
        assert_eq!(find_rotations(197), vec![719, 971]);
    }
}
